/*
 * @lc app=leetcode.cn id=895 lang=typescript
 *
 * [895] 最大频率栈
 */

// @lc code=start
class FreqStack {
    maxFreq: number // 最大频率
    valToFreq: Map<number, number>
    freqToVals: Map<number, Array<number>>
    constructor() {
        this.maxFreq = 0
        this.valToFreq = new Map()
        this.freqToVals = new Map()
    }

    push(val: number): void {
        // 修改 VF 表：val 对应的 freq 加一
        const freq = (this.valToFreq.get(val) ?? 0) + 1
        this.valToFreq.set(val, freq)
        // 修改 FV 表：在 freq 对应的列表加上 val
        if (!this.freqToVals.has(freq)) {
            this.freqToVals.set(freq, [])
        }
        this.freqToVals.get(freq)!.push(val)
        // 更新 maxFreq
        this.maxFreq = Math.max(this.maxFreq, freq)
    }

    pop(): number {
        // 修改 FV 表：pop 出一个 maxFreq 对应的元素 v
        const vals = this.freqToVals.get(this.maxFreq) ?? []
        const v = vals.pop()
        // 修改 VF 表：v 对应的 freq 减一
        const freq = (this.valToFreq.get(v!) ?? 1) - 1
        this.valToFreq.set(v!, freq)
        if (!vals.length) {
            // 如果 maxFreq 对应的元素空了
            this.maxFreq--
        }
        return v!
    }
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * var obj = new FreqStack()
 * obj.push(val)
 * var param_2 = obj.pop()
 */
// @lc code=end

